//
// Created by Administrator on 2021/8/13.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>

using namespace std;

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        // bfs
        int n = (int) s.size();
        vector<int> ans(n, n);
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (s[i] == c) {
                ans[i] = 0;
                q.emplace(i);
            }
        }
        while (!q.empty()) {
            int p = q.front();
            q.pop();
            if (p - 1 >= 0 and ans[p - 1] == n) {
                ans[p - 1] = ans[p] + 1;
                q.emplace(p - 1);
            }
            if (p + 1 < n and ans[p + 1] == n) {
                ans[p + 1] = ans[p] + 1;
                q.emplace(p + 1);
            }
        }
        return ans;

    }
};

class Solution2 {
public:
    vector<int> shortestToChar(string s, char c) {
        // 两次遍历
        int n = (int) s.size();
        vector<int> res(n, n - 1);
        // 从左往右开始遍历
        res[0] = s[0] == c ? 0 : res[0];
        for (int i = 1; i < n; ++i) {
            res[i] = s[i] != c ? res[i - 1] + 1 : 0;
        }
        // 从右往左开始遍历
        res[n - 1] = s[n - 1] == c ? 0 : res[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            // 这里需要去
            res[i] = min(res[i], s[i] != c ? res[i + 1] + 1 : 0);
        }
        return res;
    }
};

int main() {
    Solution solution;
//    vector<int> ans = solution.shortestToChar("loveleetcode", 'e');
    vector<int> ans = solution.shortestToChar("aaab", 'b');
    for (int &x:ans) cout << x << endl;
    return 0;
}
